Fischer-Lynch-Paterson theorem
Fischer-Lynch-Paterson result,
FLP,
FLP theorem,
FLP impossibility result
#distributed_computing
#distributed_computing
Theorem
Fischer-Lynch-Paterson (FLP) result suggests that you cannot have (deterministic algorithm for achieving consensus) agreement in an asynchronous message passing system if even one crash failure is allowed, unless the model is augmented in some way, e.g. randomization or failure detectors.
Notes
- may design randomized consensus algorithms that achieve safety and liveness with high probability
- consensus protocol rules: agreement, termination, validity
- consider: synchrony and partial synchrony
See also
References
- Fischer MJ, Lynch NA, Paterson MS. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM). 1985 Apr 1;32(2):374-82. https://doi.org/10.1145/3149.214121 https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
- https://www.cs.yale.edu/homes/aspnes/pinewiki/FischerLynchPaterson.html
- https://shachaf.net/w/flp
- https://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flp-impossibility/
- https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/
- https://decentralizedthoughts.github.io/2019-12-15-asynchrony-uncommitted-lower-bound/